package problems;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

import lib.MathLib;

public class Euler087 extends AbstractEuler {

	private static final int LIMIT = 50000000;
	
	@Override
	public Number calculate() {
		//each candidate that is to be counted consists of three numbers, each from a separate collection;
		//pre-compile the lists of these numbers first.
		List<Long> primeSquares =	primePowers(2, LIMIT);
		List<Long> primeCubes =		primePowers(3, LIMIT);
		List<Long> primeFourths =	primePowers(4, LIMIT);
		
		//since there might be duplicates in the answers, put them in a Set instead of simply counting them
		Set<Long> sumsBelowLimit = new HashSet<Long>();
		
		
		//nest the adder loops from big to small; that way, we're done sooner than the other way around.
		nextFourth:
		for (Long fourth : primeFourths) {
			nextCube:
			for (Long cube : primeCubes) {
				long subTotal = fourth + cube;
				if (subTotal >= LIMIT) continue nextFourth; //no sense in continuing with adding more cubes, because they are all bigger anyway
				for (Long square : primeSquares) {
					long sum = subTotal + square;
					if (sum < LIMIT) {
						sumsBelowLimit.add(sum);
					} else {
						continue nextCube; //no sense in continuing with adding more squares, because they are all bigger anyway
					}
				}
			}
		}
		
		//the number of unique counted sums below the limit
		return sumsBelowLimit.size();
	}
	
	/**
	 * Generates lists of all numbers below a certain limit that are primes raised to a certain power
	 * @param power The power to raise the primes to
	 * @param limit The limit that all numbers in the returned list must remain under
	 * @return a List of Longs that all match the requirements provided
	 */
	private List<Long> primePowers(int power, int limit) {
		List<Long> primePowers = new ArrayList<Long>();
		
		for (int i = 1; ; i++) {
			long prime = MathLib.getPrime(i);
			long primePower = prime;
			for (int p = 2; p <= power; p++) primePower *= prime;
			if (primePower >= limit) break;
			primePowers.add(primePower);
		}
		
		return primePowers;
	}

	@Override
	protected Number getCorrectAnswer() {
		return 1097343;
	}

}
